In
number theory, an
odd integer ''n'' is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base ''a'', if ''a'' and ''n'' are
coprime, and
:
where
is the
Jacobi symbol.
If ''n'' is an odd
composite integer that satisfies the above congruence, then ''n'' is called an Euler–Jacobi pseudoprime (or, more commonly, an Euler pseudoprime) to base ''a''.
Properties
The motivation for this definition is the fact that all
prime numbers ''n'' satisfy the above equation, as explained in the
Euler's criterion In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,
Let ''p'' be an odd prime and ''a'' be an integer coprime to ''p''. Then
:
a^ \equiv
\begin
\;\;\,1\pmod& \text ...
article. The equation can be tested rather quickly, which can be used for probabilistic
primality testing. These tests are over twice as strong as tests based on
Fermat's little theorem
Fermat's little theorem states that if ''p'' is a prime number, then for any integer ''a'', the number a^p - a is an integer multiple of ''p''. In the notation of modular arithmetic, this is expressed as
: a^p \equiv a \pmod p.
For example, if = ...
.
Every Euler–Jacobi pseudoprime is also a
Fermat pseudoprime and an
Euler pseudoprime. There are no numbers which are Euler–Jacobi pseudoprimes to all bases as
Carmichael numbers are.
Solovay
Robert Martin Solovay (born December 15, 1938) is an American mathematician specializing in set theory.
Biography
Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation ...
and
Strassen showed that for every composite ''n'', for at least ''n''/2 bases less than ''n'', ''n'' is not an Euler–Jacobi pseudoprime.
The smallest Euler–Jacobi pseudoprime base 2 is 561. There are 11347 Euler–Jacobi pseudoprimes base 2 that are less than 25·10
9 (see ) (page 1005 of
).
In the literature (for example,
), an Euler–Jacobi pseudoprime as defined above is often called simply an Euler pseudoprime.
See also
*
Probable prime
References
{{DEFAULTSORT:Euler-Jacobi Pseudoprime
Pseudoprimes